МІНІСТЕРСТВО ОСВІТИ І НАУКИ,МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
кафедра БІТ
З В І Т
до лабораторної роботи №2
з курсу: «Комп'ютерні методи дослідження інформаційних процесів і систем»
на тему: «Метод Гауса для розв’язування систем лінійних
алгебраїчних рівнянь»
Мета роботи – ознайомлення з прямими методами розв’язування систем лінійних алгебраїчних рівнянь.
1. Методи розв’язування систем лінійних алгебраїчних рівнянь
Нехай задано систему лінійних алгебраїчних рівнянь:
,
де А – квадратна невироджена матриця розмірності , X – вектор-стовпець невідомих розмірності n, В – вектор-стовпець вільних членів розмірності n.
Методи розв’язування систем такого виду поділяються на дві групи : прямі та ітераційні.
1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок системи) числа арифметичних операцій.
Іншими словами, прямими методом розв’язування лінійної системи називають будь-який метод, котрий дозволяє знайти елементи вектора X з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного.
Оцінити ефективність будь-якого методу можна за допомогою таких основних характеристик:
числа операцій, необхідних для реалізації даного методу;
об’єму пам’яті;
чутливості до переносу похибок заокруглення (або обчислювальної стійкості).
Практично всі прямі методи розв’язування систем базуються на зведені матриці А до матриці простішої структури – діагональної (тоді розв’язок очевидний) або трикутної, та методів розв’язування таких систем.
До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать:
– метод Гаусса
а) класичний метод Гаусса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – операцій додавання, множення та операцій ділення (можна ними знехтувати в порівнянні з ).
Прямі методи розв’язування систем лінійних алгебраїчних рівнянь
Класичний метод Гаусса.
Розглянемо систему рівнянь четвертого порядку:
(1)
Зауважимо, що елементи вектора-стовпчика вільних членів занесені в матрицю коефіцієнтів А.
Будемо вважати, що . З першого рівняння знаходимо х1:
, (2)
де , .
З допомогою рівняння (2) можна виключити з решти рівнянь, для чого достатньо підставити праву частину (2) замість в друге, третє і четверте рівняння системи. Це і є першим кроком – кроком виключення невідомого .
Перехід від початкової системи (1) до новоствореної:
відбувається за такою формулою:
Другий крок – виключення невідомого відбувається аналогічно:
Третій крок – виключення невідомого
,
;
Останнє рівняння модифікованої системи можна переписати у вигляді:
де
або .
Отже, в результаті прямого ходу одержимо систему рівнянь:
Знаходження невідомих проводиться в оберненому ході методу Гаусса шляхом зворотніх підстановок.
Якщо п – кількість рівнянь (порядок) системи, то програмування обчислювального процесу проводиться так:
L – кількість кроків виключення ;
j – позначення другого індексу при визначенні коефіцієнта ;
і – номер рядка системи ;
k – номер стовпця.
Можна записати, що для всіх
Обернений хід: ; , .
Отже, обчислювальна схема прямого ходу методу Гаусса має вигляд:
Для
Для
Для
Для
i піддається спрощенню.
Початкове обчислення всіх коефіцієнтів c не є обов’язковим. Це випливає з наступного. Наприклад, перехід від початкової системи коефіцієнтів до наступної відбувається так:
Наприклад, коефіцієнти першого чи другого стовпця нової системи утворюються за правилом
,
або
Отже, визначивши, наприклад c12 зразу ж можна переходити до визначення коефіцієнтів нової системи і т.п. Таким чином цикли по J i по K можна об’єднати (оскільки J i K змінюються в однак...
